package zoran.wang.dp;

import java.util.Arrays;

/**
 * 动态规划
 *
 * @author wangzhuo
 * @time 2025-04-11-14:42
 */
public class DynamicProgramming {

    /**
     * 斐波那契数列，定义：求第 n 个数的值
     *
     * @param n
     * @return
     */
    public int fibonacciSequence(int n) {
        // 记录结果
        int res = 0;

        // base case
        int dp1 = 0;
        int dp2 = 1;

        // 状态转移，dp table 只需要前两个值，滚动更新
        for (int i = 2; i <= n; i++) {
            res = dp1 + dp2;
            dp1 = dp2;
            dp2 = res;
        }

        return res;
    }

    /**
     * 例题：凑硬币问题，动态规划
     *
     * @param coins  硬币面值，每种硬币可以使用多次
     * @param amount 需要凑的总金额，范围 0 <= amount <= 10^4
     * @return 凑 amount 需要的最小硬币数量，凑不出来时返回 -1
     */
    public int coinChange(int[] coins, int amount) {

        // [0,amount]
        int[] dp = new int[amount + 1];
        // 状态表初始化成一个取不到的值，注意需要取最大值，问题要取最小值
        Arrays.fill(dp, Integer.MAX_VALUE - 1);

        // base case
        dp[0] = 0;

        // 动态规划，0->amount
        for (int i = 1; i <= amount; i++) {

            // 求每种硬币的最小值
            for (int coin : coins) {

                // 子问题无解，跳过
                if (i - coin < 0) continue;

                // 求所有硬币的情况下的最小值
                int min = Math.min(dp[i], dp[i - coin] + 1);
                // 存到状态表
                dp[i] = min;
            }
        }

        // 如果计算完还是默认值，说明没有被赋值，所有子问题无解
        return (dp[amount] == Integer.MAX_VALUE - 1) ? -1 : dp[amount];
    }
}
